package problem;

public class S_121 {
    /*买卖股票的最佳时机
    *
    * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

    如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

    注意你不能在买入股票前卖出股票。
    */

    //1.暴力
    class Solution {
        public int maxProfit(int[] prices) {
            int max=Integer.MIN_VALUE;
            for(int i=0;i<prices.length-1;i++){
                for(int j=i+1;j<prices.length;j++){
                    if(prices[j]>prices[i]&&prices[j]-prices[i]>max&&prices[j]-prices[i]>=0) max=prices[j]-prices[i];
                }
            }
            return max==Integer.MIN_VALUE?0:max;
        }
    }
    //2.一次遍历
    class Solution1{
        public int maxProfit(int[] prices){
            int minprice=Integer.MAX_VALUE;
            int maxprofit=0;
            for(int i=0;i<prices.length;i++){
                if(prices[i]<minprice) minprice=prices[i];
                else if(prices[i]-minprice>maxprofit) maxprofit=prices[i]-minprice;
            }
            return maxprofit;
        }
    }
}
